/**
 *
 * by littlefean
 */
class Item {
    constructor(data, index) {
        this.data = data;
        this.index = index;
    }
}

class AnimationArray {
    ItemWidth = 40;    // 与LESS文件里的@L保持一致
    ItemMargin = 10;

    /**
     *
     * @param arr {Array} [number] 0~100
     * @param ele {HTMLElement}  <div> empty </div>
     */
    constructor(arr, ele) {
        this.arr = arr;

        /**
         * 绑定了对应原始下标的数组  // [(n, 0), (n, 1), (n, 2)...]
         * 之所以绑定原始下标是因为为了能够方便的获取到html元素
         * @type {*[]}
         */
        this.dataArr = [];
        for (let i = 0; i < arr.length; i++) {
            this.dataArr.push(new Item(arr[i], i));
        }

        this.bindEle = ele;
        this.bindEle.classList.add("AniArr");

        this.animtaionStepTime = 80;  // 每一次动画毫秒数

        // 初始化显示
        let index = 0;
        for (let number of arr) {
            let itemEle = div("ArrayItem", number.toString());
            itemEle.style.left = `${(this.ItemWidth + this.ItemMargin) * index}px`;

            itemEle.style.width = `${this.ItemWidth}px`;
            itemEle.style.height = `${this.ItemWidth}px`;
            itemEle.style.lineHeight = `${this.ItemWidth}px`;
            itemEle.style.backgroundColor = `rgba(${255 * (number / 100)}, 100, ${255 * (1 - number / 100)})`;
            itemEle.style.color = "white";

            this.bindEle.appendChild(itemEle);
            index++;
        }

        // 创造双指针
        this.leftPointer = div("pointer", "↑");
        this.leftPointer.style.color = "red";
        this.rightPointer = div("pointer", "↑");
        this.bindEle.appendChild(this.leftPointer);
        this.bindEle.appendChild(this.rightPointer);

        // 创造辅助数组 （归并排序使用）
        this.helpList = div("helpList", "");
        this.bindEle.appendChild(this.helpList);

        // 创造框框表示
        this.window = div("window", "");
        this.bindEle.appendChild(this.window);

        // 创造一个flag固定不动
    }

    /**
     * 在index位置放置一个光圈爆炸效果
     * @param index
     */
    setCircle(index) {
        let duration = 200;  // 0.2s
        let ele = div("circle", "");
        ele.style.left = this.getLeftCss(index);

        this.bindEle.appendChild(ele);

        setTimeout(() => {
            this.bindEle.removeChild(ele);
        }, duration);
    }

    finish(t) {
        setTimeout(() => {
            this.bindEle.style.backgroundColor = "green";
        }, t)
    }

    /**
     * 将某一个元素突出表示，可能表示这个元素已经排序好了
     * @param index
     */
    setMark(index) {
        this.bindEle.childNodes[index].classList.add("mark");
    }

    /**
     * 在某一个下标位置标记，不随元素移动而移动
     * @param index
     */
    setFlag(index) {
        let flagEle = div("flag", "🎯");
        flagEle.style.left = this.getLeftCss(index);
        this.bindEle.appendChild(flagEle);
    }

    getLeftCss(number) {
        return `${(this.ItemWidth + this.ItemMargin) * number}px`;
    }

    setMoveCss(index, leftIndex, delay) {
        if (index >= this.bindEle.childNodes.length) {
            console.log("没找到", index, "无法设置它为", leftIndex);
            return;
        }
        setTimeout(() => {
            this.bindEle.childNodes[index].style.left = `${(this.ItemWidth + this.ItemMargin) * leftIndex}px`;
        }, delay)
    }

    /**
     * 强行修改数组动画
     * @param i i位置上的元素
     * @param number 修改数值
     */
    forceChange(i, number) {
        this.bindEle.childNodes[i].style.backgroundColor = color100Str(number);
        this.bindEle.childNodes[i].style.innerText = number.toString();
    }

    /**
     * 生成一个某一个位置移动到某一个位置上的影子动画
     * @param i
     * @param j
     * @param delay  延迟执行毫秒数
     * @param dur  持续时间毫秒数
     * 失败了，bug多
     */
    boxShadowMove(i, j, delay, dur) {
        setTimeout(() => {
            let shadowEle = divItem(this.dataArr[i].data);
            shadowEle.style.top = "0";
            this.bindEle.appendChild(shadowEle);
            shadowEle.style.top = "200px";
            shadowEle.style.left = this.getLeftCss(j);
            shadowEle.style.transition = "all 1s";
            console.log(shadowEle);
            // setTimeout(() => {
            //     this.bindEle.removeChild(shadowEle);
            // }, dur);
        }, delay);
    }

    swap(i, j, delay) {
        if (i === j) {
            return;
        }
        // 交换代码
        let temp = this.dataArr[i];
        this.setMoveCss(this.dataArr[j].index, i, delay);
        // setTimeout(() => {
        //     this.bindEle.childNodes[this.dataArr[j].index].style.animationName = `jumpAni${rand01()}`;
        //     this.bindEle.childNodes[this.dataArr[i].index].style.animationName = `jumpAni${rand01()}`;
        // }, delay);


        this.dataArr[i] = this.dataArr[j];  // j --> i
        // i --> j
        this.setMoveCss(temp.index, j, delay);
        this.dataArr[j] = temp;  // i --> j
    }

    /**
     * 选择排序
     * 交换过于频繁
     */
    selectSort() {
        let step = 0;  // 动画步数
        let st = this.animtaionStepTime; // 每一步用多少毫秒;
        this.rightPointer.style.left = this.getLeftCss(1);
        for (let i = 0; i < this.dataArr.length - 1; i++) {
            for (let j = i + 1; j < this.dataArr.length; j++) {
                if (this.dataArr[i].data > this.dataArr[j].data) {
                    this.swap(i, j, step * st);
                }

                setTimeout(() => {
                    // 更新指针位置
                    this.rightPointer.style.left = this.getLeftCss(j);
                    this.leftPointer.style.left = this.getLeftCss(i);
                }, step * st);
                step++;
            }
            setTimeout(() => {
                // 更新指针位置
                this.setMark(this.dataArr[i].index);
            }, step * st);
        }
        this.finish(step * st);
    }

    /**
     * 选择排序的优化
     *  bug
     */
    selectSort1() {
        let step = 0;  // 动画步数
        this.rightPointer.style.left = this.getLeftCss(1);
        for (let i = 0; i < this.dataArr.length; ++i) {
            let minItem = this.dataArr[i];

            for (let j = i; j < this.dataArr.length; j++) {
                if (this.dataArr[j].data < minItem.data) {
                    minItem = this.dataArr[j];
                }

                setTimeout(() => {
                    // 更新指针位置
                    this.rightPointer.style.left = this.getLeftCss(i);
                    this.leftPointer.style.left = this.getLeftCss(j);
                }, step * this.animtaionStepTime);
                step++;
            }
            this.swap(i, minItem.index, step * this.animtaionStepTime);
        }
    }

    bubbleSort() {
        let step = 0;
        for (let endLoc = this.arr.length - 1; endLoc > 0; endLoc--) {
            for (let i = 0; i < endLoc; i++) {

                if (this.dataArr[i].data <= this.dataArr[i + 1].data) {
                    // ...
                } else {
                    this.swap(i, i + 1, step * this.animtaionStepTime);
                }
                setTimeout(() => {
                    // 更新指针位置
                    this.rightPointer.style.left = this.getLeftCss(i);
                    this.leftPointer.style.left = this.getLeftCss(i + 1);
                }, step * this.animtaionStepTime);
                step++;
            }
            setTimeout(() => {
                this.setMark(this.dataArr[endLoc].index);
            }, step * this.animtaionStepTime);
        }
        this.finish(step * this.animtaionStepTime);
    }

    insertSort() {
        let step = 0;
        // 我想做到 0~i 上有序
        for (let i = 1; i < this.arr.length; i++) {
            for (let j = i - 1; j >= 0; j--) {
                if (this.dataArr[j].data <= this.dataArr[j + 1].data) {
                    break;
                } else {
                    this.swap(j, j + 1, step * this.animtaionStepTime);
                }
                setTimeout(() => {
                    // 更新指针位置
                    this.rightPointer.style.left = this.getLeftCss(i);
                    this.leftPointer.style.left = this.getLeftCss(j);
                }, step * this.animtaionStepTime);
                step++;
            }
        }
        this.finish(step * this.animtaionStepTime);
    }

    mergeSort() {
        let step = 0;
        this.helpList.style.display = "block";
        this.window.style.display = "block";
        /**
         * 合并两个数组连续区间部分，假设两个区间已经递增有序
         * .... [left, mid][mid+1 right] ....
         */
        let mg = (left, mid, right) => {

            let p1 = left;
            let p2 = mid + 1;

            let updateWindow = () => {
                setTimeout(() => {
                    this.helpList.style.left = this.getLeftCss(left);
                    this.window.style.left = this.getLeftCss(left);
                    this.window.style.width = `${this.ItemWidth * (right - left + 1) + this.ItemMargin * (right - left)}px`;
                }, step * this.animtaionStepTime);
            }
            let updatePoint = (l, r) => {
                setTimeout(() => {
                    // 更新指针位置
                    this.leftPointer.style.left = this.getLeftCss(l);
                    this.rightPointer.style.left = this.getLeftCss(r);
                }, step * this.animtaionStepTime);
            }

            let helpArr = [];


            setTimeout(() => {
                // 清空辅助数组element
                this.helpList.innerHTML = "";
            }, step * this.animtaionStepTime);

            // 合并1
            while (p1 <= mid && p2 <= right) {
                if (this.dataArr[p1].data <= this.dataArr[p2].data) {
                    helpArr.push(this.dataArr[p1]);
                    p1++;
                    //
                    // this.boxShadowMove(p1, len - 1, step * this.animtaionStepTime, 200);

                } else {
                    helpArr.push(this.dataArr[p2]);
                    p2++;
                }
                step++;
                let d = arrLast(helpArr).data;
                setTimeout(() => {

                    this.helpList.appendChild(divHelpItem(d.toString()));
                }, step * this.animtaionStepTime);
                updateWindow();
                updatePoint(p1, p2);
            }
            // 合并2
            while (p1 <= mid) {
                helpArr.push(this.dataArr[p1]);
                let d = arrLast(helpArr).data;
                setTimeout(() => {
                    this.helpList.appendChild(divHelpItem(d.toString()));
                }, step * this.animtaionStepTime);
                p1++;
                step++;
                updateWindow();
                updatePoint(p1, p2);
            }
            // 合并3
            while (p2 <= right) {
                helpArr.push(this.dataArr[p2]);
                let d = arrLast(helpArr).data;
                setTimeout(() => {
                    this.helpList.appendChild(divHelpItem(d.toString()));
                }, step * this.animtaionStepTime);
                p2++;
                step++;
                updateWindow();
                updatePoint(p1, p2);
            }
            updateWindow();
            // 辅助数组回写
            for (let i = 0; i < helpArr.length; i++) {
                this.dataArr[left + i] = helpArr[i];
                setTimeout(() => {
                    this.forceChange(left + i, helpArr[i].data);
                    this.setCircle(left + i);
                }, step * this.animtaionStepTime);
                step++;
            }
        }

        let dfs = (left, right) => {
            step++;
            if (left === right) {
                return;
            }
            setTimeout(() => {
                // 更新指针位置
                this.rightPointer.style.left = this.getLeftCss(left);
                this.leftPointer.style.left = this.getLeftCss(right);
            }, step * this.animtaionStepTime);
            let mid = Math.floor((left + right) / 2);
            dfs(left, mid);
            dfs(mid + 1, right);
            mg(left, mid, right);
        }

        dfs(0, this.arr.length - 1);
        this.finish(step * this.animtaionStepTime);
    }

    /**
     * 快速排序
     */
    quickSort() {
        let step = 0;

        this.window.style.display = "block";

        let setWindow = (a, b) => {
            setTimeout(() => {

                this.window.style.left = this.getLeftCss(a);
                this.window.style.width = `${this.ItemWidth * (b - a + 1) + this.ItemMargin * (b - a)}px`;
            }, step * this.animtaionStepTime);
        }
        let setPoint = (a, b) => {
            setTimeout(() => {
                // 更新指针位置
                this.rightPointer.style.left = this.getLeftCss(a);
                this.leftPointer.style.left = this.getLeftCss(b);
            }, step * this.animtaionStepTime);
        };
        let partition = (l, r) => {
            let i = l;
            for (let j = l; j < r; j++) {
                if (this.dataArr[j].data < this.dataArr[r].data) {
                    this.swap(i, j, step * this.animtaionStepTime);
                    i++;
                }
                setWindow(l, r);
                setPoint(i, j);
                step++;
            }
            this.swap(i, r, step * this.animtaionStepTime);
            step++;
            setPoint(i, r);
            setWindow(l, r);
            return i;
        }

        let dfs = (l, r) => {
            step++;
            if (l < r) {
                let sign = partition(l, r);

                setTimeout(() => {
                    this.setFlag(sign);
                }, step * this.animtaionStepTime);

                dfs(l, sign - 1);
                dfs(sign + 1, r);
            }
        };

        dfs(0, this.arr.length - 1);
        this.finish(step * this.animtaionStepTime);
    }

    /**
     * 堆排序
     */
    heapSort() {
        let step = 0;
        let setPoint = (a, b) => {
            setTimeout(() => {
                // 更新指针位置
                this.rightPointer.style.left = this.getLeftCss(a);
                this.leftPointer.style.left = this.getLeftCss(b);
            }, step * this.animtaionStepTime);
        };
        //编写一个堆排序 https://zhuanlan.zhihu.com/p/263560833
        //将一个数组(二叉树),调整成一个大顶堆
        /**
         * 将以i对应的非叶子节点的树调整成一个大顶堆
         * @param {Number} i 表示非叶子节点在数组中的索引
         * @param {Number} length  对多少个元素进行调整，length是在逐渐减少
         */
        let adjustHeap = (i, length) => {
            let temp = this.dataArr[i];

            setTimeout(() => {
                this.setCircle(i);
            }, step * this.animtaionStepTime);

            for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
                if (k + 1 < length && this.dataArr[k].data < this.dataArr[k + 1].data) {
                    k++;
                }
                setPoint(k, i);
                step++;
                if (this.dataArr[k].data > temp.data) {
                    this.dataArr[i] = this.dataArr[k];
                    let n = this.dataArr[k].data;
                    setTimeout(() => {
                        this.forceChange(i, n);
                        this.forceChange(k, n);
                    }, step * this.animtaionStepTime);
                    i = k;
                } else {
                    break;
                }
                setPoint(k, i);
                this.dataArr[i] = temp;
                let n = temp.data;
                setTimeout(() => {
                    this.forceChange(i, n);
                }, step * this.animtaionStepTime);
                step++;
            }
        }

        let heapSort_ = () => {
            for (let i = Math.floor(this.arr.length / 2) - 1; i >= 0; i--) {
                adjustHeap(i, this.arr.length);
                setPoint(i, i);
                step++;
            }
            for (let j = this.arr.length - 1; j > 0; j--) {
                //交换
                this.swap(0, j, step * this.animtaionStepTime);
                adjustHeap(0, j);
                setPoint(j, j);
                step++;
            }
        }
        heapSort_();
        // console.log(this.dataArr);
        this.finish(step * this.animtaionStepTime);
    }
}
